use std::{
    cell::{Ref, RefCell, RefMut},
    rc::Rc,
};

type Link<T> = Option<Rc<RefCell<Node<T>>>>;

fn some_rc_refcell<T>(value: T) -> Option<Rc<RefCell<T>>> {
    Some(Rc::new(RefCell::new(value)))
}

pub struct Deque<T> {
    head: Link<T>,
    last: Link<T>,
}

struct Node<T> {
    value: T,
    prev: Link<T>,
    next: Link<T>,
}

impl<T> Node<T> {
    fn new(value: T) -> Self {
        Node {
            value,
            prev: None,
            next: None,
        }
    }
}

impl<T> Deque<T> {
    pub fn new() -> Self {
        Deque {
            head: None,
            last: None,
        }
    }

    pub fn push_front(&mut self, value: T) {
        let mut new_node = Node::new(value);
        if let Some(old_head) = self.head.take() {
            new_node.next = Some(old_head.clone()); // take or clone
            self.head = some_rc_refcell(new_node);
            old_head.borrow_mut().prev = self.head.clone();
        } else {
            let new_node = some_rc_refcell(new_node);
            self.head = new_node.clone();
            self.last = new_node;
        }
    }

    pub fn pop_front(&mut self) -> Option<T> {
        if let Some(old_head) = self.head.take() {
            if let Some(new_head) = old_head.borrow_mut().next.take() {
                new_head.borrow_mut().prev = None;
                self.head = Some(new_head);
            } else {
                self.head = None;
                self.last = None;
            }
            Some(Rc::try_unwrap(old_head).ok().unwrap().into_inner().value)
        } else {
            None
        }
    }

    pub fn push_back(&mut self, value: T) {
        let mut new_node = Node::new(value);
        if let Some(old_last) = self.last.take() {
            new_node.prev = Some(old_last.clone()); // take or clone
            self.last = some_rc_refcell(new_node);
            old_last.borrow_mut().next = self.head.clone();
        } else {
            let new_node = some_rc_refcell(new_node);
            self.head = new_node.clone();
            self.last = new_node;
        }
    }

    pub fn pop_last(&mut self) -> Option<T> {
        if let Some(old_last) = self.last.take() {
            if let Some(new_last) = old_last.borrow_mut().prev.take() {
                new_last.borrow_mut().next = None;
                self.last = Some(new_last);
            } else {
                self.head = None;
                self.last = None;
            }
            Some(Rc::try_unwrap(old_last).ok().unwrap().into_inner().value)
        } else {
            None
        }
    }

    pub fn peek_front(&self) -> Option<Ref<T>> {
        self.head
            .as_ref()
            .map(|head| Ref::map(head.borrow(), |x| &x.value))
    }

    pub fn peek_last(&self) -> Option<Ref<T>> {
        self.last
            .as_ref()
            .map(|last| Ref::map(last.borrow(), |x| &x.value))
    }

    pub fn peek_last_mut(&mut self) -> Option<RefMut<T>> {
        self.last
            .as_ref()
            .map(|node| RefMut::map(node.borrow_mut(), |node| &mut node.value))
    }

    pub fn peek_front_mut(&mut self) -> Option<RefMut<T>> {
        self.head
            .as_ref()
            .map(|node| RefMut::map(node.borrow_mut(), |node| &mut node.value))
    }
}

impl<T> Drop for Deque<T> {
    fn drop(&mut self) {
        while self.pop_front().is_some() {}
    }
}

#[cfg(test)]
mod test {
    use super::Deque;

    #[test]
    fn peek_push() {
        let mut list = Deque::new();
        list.push_front(1);
        list.push_front(2);

        let tmp = list.peek_front().unwrap();
        // list.push_front(3); error on compile time
    }

    #[test]
    fn peek() {
        let mut list = Deque::new();
        assert!(list.peek_front().is_none());
        list.push_front(1);
        list.push_front(2);
        list.push_front(3);

        assert_eq!(&*list.peek_front().unwrap(), &3);
    }
    #[test]
    fn basics() {
        let mut list = Deque::new();

        // Check empty list behaves right
        assert_eq!(list.pop_front(), None);

        // Populate list
        list.push_front(1);
        list.push_front(2);
        list.push_front(3);

        // Check normal removal
        assert_eq!(list.pop_front(), Some(3));
        assert_eq!(list.pop_front(), Some(2));

        // Push some more just to make sure nothing's corrupted
        list.push_front(4);
        list.push_front(5);

        // Check normal removal
        assert_eq!(list.pop_front(), Some(5));
        assert_eq!(list.pop_front(), Some(4));

        // Check exhaustion
        assert_eq!(list.pop_front(), Some(1));
        assert_eq!(list.pop_front(), None);
    }
}
